#include <algorithm>
#include <cstdio>
#include <assert.h>
namespace ALC{
const int NMax=1000000;
template<class KEY,class DATA>
struct node{
        KEY k;DATA d;
        int h;
        node *left,*right;
};
#define HIGH(_) ((_)?(_)->h:0)
//template<class T>
//inline T max(T a,T b){return a>b?a:b;}
template<class KEY,class DATA>
struct AVL{
        node<KEY,DATA>* root;
        void _clean(node<KEY,DATA> *p) {
            if(!p) return ;
			if(!p->left&&!p->right) {
				delete p;
				return ;
			}
			if(p->left) _clean(p->left);
			if(p->right) _clean(p->right);
			delete p;
        }
        AVL(){_clean(root);root=NULL;}
        void clear(){_clean(root);root=NULL;}
        DATA data(KEY x){
                node<KEY,DATA> *p=root;
                while(p&&x!=p->k){
                        if(x>p->k) p=p->right;
                        else p=p->left;
                }
                assert(p);
                return p->d;
        }
		node<KEY,DATA> *_find(KEY x) {
			node<KEY,DATA> *p=root;
            while(p&&x!=p->k){
                if(x>p->k) p=p->right;
                else p=p->left;
            }
            assert(p);
            return p;
		}
        bool ishave(KEY x) {
        node<KEY,DATA> *p=root;
        while(p&&x!=p->k){
                        if(x>p->k) p=p->right;
                        else p=p->left;
                }
                return p!=NULL;
        }
        node<KEY,DATA>* getnode(KEY x) {
                node<KEY,DATA> *p=root;
                while(p){
                        node<KEY,DATA> *tmp;
                        if(x>p->k) tmp=p->right;
                        else tmp=p->left;
                        if(!tmp) break;
                        p=tmp;
                }
                return p;
        }
        node<KEY,DATA>* _LR(node<KEY,DATA>* p){
                if(!p) return NULL;
                assert(p->right);
                node<KEY,DATA>* q=p->right;
                p->right=q->left;q->left=p;
                p->h=max(HIGH(p->left),HIGH(p->right))+1;
                q->h=max(HIGH(q->left),HIGH(q->right))+1;
                return q;
        }
        node<KEY,DATA>* _RR(node<KEY,DATA>* p){
                if(!p) return NULL;
                assert(p->left);
                node<KEY,DATA>* q=p->left;
                p->left=q->right;q->right=p;
                p->h=max(HIGH(p->left),HIGH(p->right))+1;
                q->h=max(HIGH(q->left),HIGH(q->right))+1;
                return q;
        }
        node<KEY,DATA>* _insert(node<KEY,DATA>* p,KEY x,DATA y) {
                if(!p){
                        node<KEY,DATA> *q=new node<KEY,DATA>;
                        q->k=x;q->d=y;q->h=1;q->left=q->right=NULL;
                        p=q;
                }else if(x>p->k) {
                        p->right=_insert(p->right,x,y);
                        if(HIGH(p->right)>=HIGH(p->left)+2){
                                if(x<p->right->k) {
                                        p->right=_RR(p->right);
                                        p=_LR(p);
                                }else p=_LR(p);
                        }
                }else {
                        p->left=_insert(p->left,x,y);
                        if(HIGH(p->left)>=HIGH(p->right)+2){
                                if(x>p->left->k) {
                                        p->left=_LR(p->left);
                                        p=_RR(p);
                                }else p=_RR(p);
                        }
                }
                p->h=max(HIGH(p->left),HIGH(p->right))+1;
                return p;
        }
        void insert(KEY x,DATA y){if(ishave(x)) return;else root=_insert(root,x,y);}
        node<KEY,DATA>* minnode(node<KEY,DATA>* p) {
                if(!p) return NULL;
                while(p->left) p=p->left;
                return p;
        }
        node<KEY,DATA>* minnodefather(node<KEY,DATA>* p) {
                if(!p) return NULL;
                while(p->left&&p->left->left) p=p->left;
                return p;
        }
        node<KEY,DATA>* _delete(node<KEY,DATA>* p,KEY x){
                if(p->k==x) {
                        if(!p->left){node<KEY,DATA> *q=p;p=p->right;delete q;}
                        else if(!p->right){node<KEY,DATA> *q=p;p=p->left;delete q;}
                        else {
                                node<KEY,DATA> *q=minnode(p->right);//*f=minnodefather(p->right);
                                assert(q);
                                p->k=q->k;p->d=q->d;
                                p->right=_delete(p->right,q->k);
                                if(HIGH(p->left)>=HIGH(p->right)+2){
                                        if(HIGH(p->left->right)>HIGH(p->left->left)) {//x>p->left->k
                                                p->left=_LR(p->left);
                                                p=_RR(p);
                                        }else p=_RR(p);
                                }
                        }
                }else if(x>p->k) {
                        p->right=_delete(p->right,x);
                        if(HIGH(p->left)>=HIGH(p->right)+2){
                                if(HIGH(p->left->right)>HIGH(p->left->left)) {//x>p->left->k
                                        p->left=_LR(p->left);
                                        p=_RR(p);
                                }else p=_RR(p);
                        }
                }else {
                        p->left=_delete(p->left,x);
                        if(HIGH(p->right)>=HIGH(p->left)+2){
                                if(HIGH(p->right->left)>HIGH(p->right->right)) {//x<p->right->k
                                        p->right=_RR(p->right);
                                        p=_LR(p);
                                }else p=_LR(p);
                        }
                }
                if(p)p->h=max(HIGH(p->left),HIGH(p->right))+1;
                return p;
        }
        void erase(KEY x){if(ishave(x))root=_delete(root,x);}
        bool haveroot(){return root?1:0;}
        void _DFS(node<KEY,DATA> *p) {
                if(!p) return;
                printf("%d\n",p->k);
                _DFS(p->left);_DFS(p->right);
        }
        void DFS(){_DFS(root);}
		void change(KEY x,DATA y) {
			if(ishave(x)) {
				node<KEY,DATA> *p=_find(x);
				p->d=y;
			}
		}
};
};